package com.samxcode.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * You are given a string, s, and a list of words, words, that are all of the same length. Find all
 * starting indices of substring(s) in s that is a concatenation of each word in words exactly once
 * and without any intervening characters.
 * 
 * @author Sam
 *
 */
public class FindSubstring {
    
    public static void main(String[] args) {
        String[] words = {"a", "b", "a"};
        System.out.println(findSubstring("abababab", words));
    }

    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        if (words.length == 0 || s.length() == 0) {
            return res;
        }
        int wLen = words[0].length();
        // the count of special words displayed each loop
        int count;
        // the start index each matching process
        int startIndex;
        // put the given dictionary into hash map with each word's count
        HashMap<String, Integer> dict = new HashMap<String, Integer>();
        // dictionary in current matching process
        HashMap<String, Integer> curMap = new HashMap<String, Integer>();
        for (String word : words) {
            if (dict.containsKey(word))
                dict.put(word, dict.get(word) + 1);
            else
                dict.put(word, 1);
        }
        for (int i = 0; i < wLen; i++) {
            count = 0;
            startIndex = i;
            curMap.clear();
            for (int j = i; j <= s.length() - wLen; j += wLen) {
                // current word
                String sub = s.substring(j, j + wLen);
                if (dict.containsKey(sub)) {
                    // update current dictionary
                    if (curMap.containsKey(sub))
                        curMap.put(sub, curMap.get(sub) + 1);
                    else
                        curMap.put(sub, 1);
                    count++;
                    // check if count for current found word exceed given word count
                    if (curMap.get(sub) > dict.get(sub)) {
                        // shift the start index to the found word's next word and update the count
                        while (curMap.get(sub) > dict.get(sub)) {
                            String temp = s.substring(startIndex, startIndex + wLen);
                            curMap.put(temp, curMap.get(temp) - 1);
                            startIndex += wLen;
                            count--;
                        }
                    }
                    // put the start index into result, shift index to next word, and update current
                    // dictionary and count
                    if (count == words.length) {
                        res.add(startIndex);
                        String temp = s.substring(startIndex, startIndex + wLen);
                        curMap.put(temp, curMap.get(temp) - 1);
                        startIndex += wLen;
                        count--;
                    }
                } else {
                    curMap.clear();
                    startIndex = j + wLen;
                    count = 0;
                }

            }
        }
        return res;
    }
}
